package com.aikon.wht.paoshan.alg;

import com.aikon.wht.paoshan.PaoshanUtils;
import com.aikon.wht.utils.PaoshanUtils;

/**
 * 荷兰国旗问题
 * 给定一个数组arr，和一个数pivot，请把小于pivot的数放在数组的 左边，等于pivot的数放在数组的中间，大于pivot的数放在数组的 右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 *
 * 0 1 2 3 4 5     pivot=4
 *
 * l         m
 * 5 4 6 3 7 2
 * c
 * l       m
 * 2 4 6 3 7 5
 * c
 *   l     m
 * 2 4 6 3 7 5
 *   c
 *   l     m
 * 2 4 6 3 7 5
 *     c
 *   l   m
 * 2 4 7 3 6 5
 *     c
 *   l m
 * 2 4 3 7 6 5
 *     c
 *    l/m
 * 2 3 4 7 6 5
 *       c
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfNetherlandsFlag {


    public static int[] sort(int[] arr, int pivot) {
        // 小于num的位置，从0开始
        int less = 0;
        // 大于num的位置，从length-1开始
        int more = arr.length - 1;
        // 游标，从0开始
        int current = 0;
        while (current <= more) {
            if (arr[current] == pivot) {
                current++;
            } else if (arr[current] < pivot) {
                PaoshanUtils.swap(arr, less, current);
                less++;
                current++;
            } else {
                PaoshanUtils.swap(arr, more, current);
                more--;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = sort(new int[]{1, 3, 4, 6, 2, 3, 5, 6, 4, 7, 3}, 3);
        for (Integer i : arr) {
            System.out.println(i);
        }
    }
}